package 搜索.DFS;

import java.util.ArrayList;
import java.util.List;

/*
解题思路：
    这题和130题有点类似，都是从边界往内寻找。
    这题呢我们从边界出发，假设先从上边出发，也就是太平洋。  靠近上边的水流一定都可以流入太平洋，那么我们只需要将“上边”遍历，找到高度比它高的，就可以通过
    它流入太平洋。其它三条边也是这样。只不过右边和下边是可以流入大西洋。

    解释一下：题目说高度高的可以向高度低的或者高度相等的流动。 也就是说，只要比上边的水流的高度高，或者相等，那么该水流就可以流到上边，而上边又和太平洋
    相连，即该水流可流入太平洋。
    这样，两轮循环，一轮用来找到可以流入太平洋的水流， 一轮找到可以流入大西洋的水流，把它们分别放入两个boolean数组中，
    然后再来一次整个数组遍历，如果有一个水流 即可流入太平洋也可流入大西洋（toPa[i][j] && toAt[i][j]）。那么它就是我们要寻找的。
    把它的坐标放入res，返回即可。
    本题的重点就是 中间的水流可以通过四条边的水流 流入对应的海洋。



 */
public class 太平洋大西洋水流问题_417 {

    public static void main(String[] args) {
        太平洋大西洋水流问题_417 t = new 太平洋大西洋水流问题_417();
        int[][] maxtrix = new int[][]{{1, 2, 2, 3, 5}, {3, 2, 3, 4, 4}, {2, 4, 5, 3, 1}, {6, 7, 1, 4, 5}, {5, 1, 1, 2, 4}};
        System.out.println(t.pacificAtlantic(maxtrix));
    }

    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> res = new ArrayList<>();

        if (matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }

        int r = matrix.length;//行数，可以看成y轴
        int c = matrix[0].length;//列数，可以看成x轴
        boolean[][] toPa = new boolean[r][c];
        boolean[][] toAt = new boolean[r][c];

        for (int i = 0; i < r; i++) {//要去选择第一列和最后一列，  变化的是行数，列数是固定的0和c-1，所以这里循环条件用行（r）
            //第一次遍历，会给一个初始高度，到后面要进行比较的时候再用matrix[r][c] 来替换初始高度
            DFS(i, 0, matrix, toPa, Integer.MIN_VALUE);//遍历第一列  即正方形的左边，它用DFS来遍历哪些能够通过它 ，到达太平洋（Pa）的水流。下面的同理
            DFS(i, c - 1, matrix, toAt, Integer.MIN_VALUE);//遍历最后一列
        }

        for (int i = 0; i < c; i++) {
            DFS(0, i, matrix, toPa, Integer.MIN_VALUE);//遍历第一行
            DFS(r - 1, i, matrix, toAt, Integer.MIN_VALUE);//遍历最后一行
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {//遍历整个二维数组
                if (toPa[i][j] && toAt[i][j]) {//如果该水流即能到达pa也能到达at，就是我们的目标
                    List<Integer> cur = new ArrayList<>();
                    cur.add(i);
                    cur.add(j);
                    res.add(cur);
                }
            }
        }
        return res;
    }

    int[][] directions = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    public void DFS(int r, int c, int[][] matrix, boolean[][] toSea, int height) {
        if (r < 0 || r >= matrix.length
                || c < 0 || c >= matrix[0].length
                || toSea[r][c]
                || matrix[r][c] < height) {//matrix[r][c] < height即现在遍历到的水流高度，比之前那个要小，这是不可以的，因为只有现在的高度大于之前的高度，才可以通过之前的流入海洋
            return;
        }
        toSea[r][c] = true;//它能够到达大西洋或者太平洋。要根据具体是那个在那个循环调用的。
        for (int[] dir : directions) {
            /*
            r + dir[0]：相当于横坐标向四个方向遍历
            c + dir[1]：相当于纵坐标向四个方向遍历
             */
            DFS(r + dir[0], c + dir[1], matrix, toSea, matrix[r][c]);//这时候高度就会更新为matrix[r][c]
        }

    }
}
